package sit.engreal.leetcode.problems100;

import java.util.*;

/**
 * <a herf="https://leetcode.cn/problems/3sum/">15. 三数之和</a>
 */
public class LeetCode15 {
    public List<List<Integer>> threeSum(int[] nums) {
        int zeroCount = 0;
        int[] positive = new int[nums.length];
        int positiveCount = 0;
        int[] negative = new int[nums.length];
        int negativeCount = 0;
        for (int num : nums) {
            if (num > 0) {
                positive[positiveCount] = num;
                positiveCount++;
            } else if (num < 0) {
                negative[negativeCount] = -num;
                negativeCount++;
            } else {
                zeroCount++;
            }
        }
        Arrays.sort(positive, 0, positiveCount);
        Arrays.sort(negative, 0, negativeCount);

        final List<List<Integer>> answer = new ArrayList<>();
        int v;

        // + --
        v = 0;
        for (int k = 0; k < positiveCount; k++) {
            if (v == positive[k]) {
                continue;
            }
            v = positive[k];
            int i = 0;
            int j = negativeCount - 1;
            while (i < j) {
                if (negative[i] + negative[j] < v) {
                    do {
                        i++;
                    } while (i < j && negative[i] == negative[i - 1]);
                } else if (negative[i] + negative[j] > v) {
                    do {
                        j--;
                    } while (i < j && negative[j] == negative[j + 1]);
                } else {
                    final ArrayList<Integer> tuple = new ArrayList<>(3);
                    tuple.add(-negative[j]);
                    tuple.add(-negative[i]);
                    tuple.add(v);
                    answer.add(tuple);
                    do {
                        j--;
                    } while (i < j && negative[j] == negative[j + 1]);
                }
            }
        }

        // 0 - +
        if (zeroCount > 0) {
            int i = 0;
            int j = 0;
            while (i < negativeCount && j < positiveCount) {
                boolean nextNegative = false;
                boolean nextPositive = false;
                if (negative[i] < positive[j]) {
                    nextNegative = true;
                } else if (negative[i] > positive[j]) {
                    nextPositive = true;
                } else {
                    final ArrayList<Integer> tuple = new ArrayList<>(3);
                    tuple.add(-negative[i]);
                    tuple.add(0);
                    tuple.add(positive[j]);
                    answer.add(tuple);
                    nextNegative = true;
                    nextPositive = true;
                }
                if (nextNegative) {
                    do {
                        i++;
                    } while (i < negativeCount && negative[i] == negative[i - 1]);
                }
                if (nextPositive) {
                    do {
                        j++;
                    } while (j < positiveCount && positive[j] == positive[j - 1]);
                }
            }
        }

        // 0 0 0
        if (zeroCount >= 3) {
            final ArrayList<Integer> tuple = new ArrayList<>(3);
            tuple.add(0);
            tuple.add(0);
            tuple.add(0);
            answer.add(tuple);
        }

        // - ++
        v = 0;
        for (int k = 0; k < negativeCount; k++) {
            if (v == negative[k]) {
                continue;
            }
            v = negative[k];
            int i = 0;
            int j = positiveCount - 1;
            while (i < j) {
                if (positive[i] + positive[j] < v) {
                    do {
                        i++;
                    } while (i < j && positive[i] == positive[i - 1]);
                } else if (positive[i] + positive[j] > v) {
                    do {
                        j--;
                    } while (i < j && positive[j] == positive[j + 1]);
                } else {
                    final ArrayList<Integer> tuple = new ArrayList<>(3);
                    tuple.add(-v);
                    tuple.add(positive[i]);
                    tuple.add(positive[j]);
                    answer.add(tuple);
                    do {
                        j--;
                    } while (i < j && positive[j] == positive[j + 1]);
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        final LeetCode15 demo = new LeetCode15();
        System.out.println(demo.threeSum(new int[]{-10, 1, 2, 2, 8, 9}));
        System.out.println(demo.threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }
}
